#include "main.h"
#include <cstdlib>


/*
 * Randomized divide and conquer
 * 
 * Use randomized partition from quick sort
 * expected running time: theta(n)
 * worst case: theta(n^2)
 */
 
 

inline void exchange(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

inline int choosePivot(int len)
{
	static double rr = 1.0 / RAND_MAX;

	int r = rand();
	double d = r * rr * (len-1);
	return (int)d;
}

int partition(int* array, int beg, int end)
{
	if (beg == end) { return beg; }
	
	int pos = choosePivot(end - beg + 1);
	exchange(array[beg], array[pos]);
	
	int pivot = array[beg];
	int i = 0, j = 1;
	for (; j <= end; ++j)
	{
		if (array[j] < pivot)
		{
			i++;
			exchange(array[j], array[i]);
		}
	}
	exchange(array[beg], array[i]);
	
	return i;
}

int randomizedSelect(int* array, int beg, int end, int k)
{
	if (k > end + 1)
	{
		return 0;
	}
	
	int i = partition(array, beg, end);
	if (i == k-1)
	{
		return array[i];
	}
	else if (i > k-1)
	{
		return randomizedSelect(array, beg, i-1, k);
	}
	else
	{
		return randomizedSelect(array, i+1, end, k);
	}
}